package 分发糖果;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/4/23 11:25
 * @description:
 */
public class Solution {
    public int candy(int[] ratings) {
        // greedy
        // 从前向后遍历，先只看左手边的孩子
        // 局部最优：只要右手边的孩子评分更高，那么就分给右手边孩子更多的糖果。
        // 局部最优：只要左手边的孩子评分更高，那么就分给左手边孩子更多的糖果。
        // 全局最优：保证了所有右手边的孩子都分得了更多的糖果 + 保证了所有左手边的孩子都分得了更多的糖果 ==> 全局最优

        int number = 0;
        int[] candyVec = new int[ratings.length];
        Arrays.fill(candyVec, 1);
        // 保证右边大于左边
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candyVec[i] = candyVec[i - 1] + 1;
            }
        }
        // 保证左边大于右边
        for (int i = ratings.length - 1; i > 0; i--) {
            if (ratings[i] < ratings[i - 1]) {
                candyVec[i - 1] = candyVec[i] + 1;
            }
        }
        return Arrays.stream(candyVec).sum();
    }
}
